1. Field of the Invention
The present invention relates to a hierarchical lattice generating method, apparatus, and program for generating a hierarchical lattice at a boundary part of an object in accordance with a desired resolution when a computer simulation is executed.
2. Description of the Related Art
Many computer simulators that use hierarchical lattices have been developed. Examples of detailed descriptions of such computer simulators are John Strain, “Fast Tree-Based Redistancing for Level Set Computations”, in the Journal of Computational Physics 152, p. 664–686 (1999) and Michael Griebel, Gerhard Zumbusch, “Parallel Adaptive Subspace Correction Schemes with Applications to Elasticity” in “Computer Methods in Applied Mechanics and Engineering” 184 p. 303–332(2000) and the references given by these articles.
These articles describe an arrangement wherein the resolution (hierarchy) of areas in the neighborhood of the boundary surfaces of objects that need to be represented in high resolution can be raised as desired. According to this arrangement, the areas in the neighborhood of the boundary surfaces are mathematically represented by a “filter space” so that the resolution can be appropriately defined. A similar arrangement has been proposed in the field of computer graphics as a method for representing objects (see Japanese Laid-Open Patent Publications (Kokai) Nos. 6-215076, 9-198524, and 2001-52206.
When executing many computer simulations, it is necessary to input the form of the object, and in particular the form of the boundary parts of the object. In many cases, the boundary surfaces which form such boundary parts have a codimension 1. When a simulation is performed within a two-dimensional plane, boundary surfaces are constructed of curves or broken lines as piecewise linear figures. When a simulation is performed within a three-dimensional space, boundary surfaces are constructed of two-dimensional curved surfaces and curved surfaces composed of piecewise flat surfaces.
These boundary parts that include boundary surfaces often have an important role in computer simulations as the regions that apply boundary conditions for partial differential equations. Therefore, such boundary parts should be represented using deep (i.e., fine) hierarchical lattices. As one example, the aforementioned reference John Strain, “Fast Tree-Based Redistancing for Level Set Computations”, Journal of Computational Physics 152, p. 664–686(1999) proposes a calculation method for raising the resolution of boundary parts to a desired precision by using a method called the “level set method”. The level set method proposed by Strain will be described briefly below.
As one example, the level set method is described in detail in J. A. Sethian “Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry Fluid Mechanics, Computer Vision, and Materials Science” Cambridge University Press that was published in 1996.
The “level set method” sets coordinates that are determined according to the natural distances within a region that is perpendicular to a boundary surface with a codimension 1, and regards the values of these coordinates as a scalar function within the region. In mathematical terms, the method is based upon the fact that if the boundary surface is sufficiently smooth, at the tubular neighborhoods of the boundary surface the normal bundle and tubular neighborhoods are diffeomorphisms.
In conventional practice, the zero point of the perpendicular coordinates is set on the boundary surface in the level set method. Normally, the perpendicular coordinates of points located far away from the boundary surface become mathematically meaningless. The level set function, however, does not consider such mathematical details and uses values that are determined by numerical computations as coordinate values. In this way, the level set method is not generally well-defined, but is a sufficiently effective method for boundary surfaces that are sufficiently smooth within a Euclidean space. Strain's method changes the resolution in accordance with the magnitude (that is, the distance from the boundary surface in the direction of a codimensional normal) of the level set function.
Japanese Laid-Open Patent Publications (Kokai) Nos. 6-215076, 9-198524, and 2001-52206 propose similar methods for controlling the resolution using a distance function as methods for changing the resolution in the field of computer graphics. The basic concept of these methods is almost the same as Strain.
However, in Japanese Laid-Open Patent Publication (Kokai) No. 9-198524, areas at and close to the boundary surfaces of the object that are related to the raising and lowering of the resolution are not in the form of a mathematical filter space, which differs from resolution spaces (hierarchical spaces) in the field of computer simulation, as exemplified by the teachings of Strain.
A level set function is normally found by calculating the distance from the boundary surface in the direction of a codimensional normal. Strain, meanwhile, finds a level set function by calculating the distance from a piecewise segmental curve.
However, the computational cost of calculating such distances with a computer are normally high, and various problems are known to occur for such floating point calculations. Accordingly, algorithms that include distance calculations suffer from the same problems.